#include <iostream>
#include <list>
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
private:
    TreeNode* p;
    TreeNode* q;
    TreeNode* same;
    int dfs(TreeNode* node) {
        int self = 0;
        int left = 0;
        int right = 0;
        if (node == p || node == q) {
            self = 1;
        }
        if (node->left != nullptr) {
            left = dfs(node->left);
            if (left == 2) {
                return 2;
            }
        }
        if (node->right != nullptr) {
            right = dfs(node->right);
            if (right == 2) {
                return 2;
            }
        }
        if (self + left + right == 2) {
            same = node;
        }
        return self + left + right;
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr) {
            return nullptr;
        }
        if (p == q) {
            return p;
        }
        this->p = p;
        this->q = q;
        dfs(root);
        return same;
    }
};